package leetcode.str;

/*实现 strStr() 函数。

        给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/implement-strstr
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

public class Test28 {

    public static void main(String[] args) {
        int index = strStr("aabaaabaaac", "aabaaac");
        System.out.println(index);
    }

    //aabb ab
    public static int strStr(String haystack, String needle) {
        char[] s1 = haystack.toCharArray();
        char[] s2 = needle.toCharArray();
        if (s2.length == 0) {
            return 0;
        }
        //先求next
        int[] next = new int[needle.length()];
        int j = 0;
        next[0] = j;
        for (int i = 1; i < needle.length(); i++) {
            while (j > 0 && s2[j] != s2[i]) {
                j = next[j - 1];
            }
            if (s2[i] == s2[j]) {
                j++;
            }
            next[i] = j;
        }
        int m = 0, n = 0;
        while (m < s1.length) {
            if (s1[m] == s2[n]) {
                m++;
                n++;
                if (n == s2.length) {
                    return m - n;
                }
            } else if (n == 0) {
                m++;
            } else {
                n = next[n - 1];
            }
        }

        return -1;
    }
}
